// 版权所有（c）2017 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package field

import "math/bits"

// uint128将128位数字作为两个64位分支，用于
// 位。Mul64和位。添加64个内部函数。
type uint128 struct {
	lo, hi uint64
}

// mul64返回a*b。
func mul64(a, b uint64) uint128 {
	hi, lo := bits.Mul64(a, b)
	return uint128{lo, hi}
}

// addMul64返回v+a*b。
func addMul64(v uint128, a, b uint64) uint128 {
	hi, lo := bits.Mul64(a, b)
	lo, c := bits.Add64(lo, v.lo, 0)
	hi, _ = bits.Add64(hi, v.hi, c)
	return uint128{lo, hi}
}

// shifttrightby51返回a>>51。假设a最多为115位。
func shiftRightBy51(a uint128) uint64 {
	return (a.hi << (64 - 51)) | (a.lo >> 51)
}

func feMulGeneric(v, a, b *Element) {
	a0 := a.l0
	a1 := a.l1
	a2 := a.l2
	a3 := a.l3
	a4 := a.l4

	b0 := b.l0
	b1 := b.l1
	b2 := b.l2
	b3 := b.l3
	b4 := b.l4

	// 肢体乘法与笔和纸的柱状乘法类似，但
	// 使用51位肢体而不是数字。
	// 
	// a4 a3 a2 a1 a0 x 
	// b4 b3 b2 b1 b0=
	// ---------------------------
	// a4b0 a3b0 a2b0 a1b0 a0b0+
	// a4b1 a3b1 a2b1 a1b1 a0b1+
	// a4b2 a3b2 a2b2 a1b2 a0b2+
	// a4b3 a3b3 a2b3 a1b3 a0b3+
	// a4b4 a3b4 a2b4 a1b4 a0b4=
	// --------------------------------------
	// r8 r7 r6 r4 r3 r2 r0 
	// 
	// 减少标识（a*2²）⁵⁵ + b=a*19+b）到
	// 减少会溢出255位的分支。r5*2²⁵⁵ 变成19*r5，
	// r6*2³⁰⁶ 变成19*r6*2⁵1等。
	// 
	// 可以同时进行乘法的归约。对于
	// 例如，我们不计算r5：每当乘法
	// 的结果属于r5，比如a1b4，我们将其乘以19，然后将结果加上r0。
	// 
	// a4b0 a3b0 a2b0 a1b0 a0b0+
	// a3b1 a2b1 a1b1 a0b1 19×a4b1+
	// a2b2 a1b2 a0b2 19×a4b2 19×a3b2+
	// a1b3 a0b3 19×a4b3 19×A3B319×a2b3+
	// a0b4 19×a4b4 19×a3b4 19×a1b4=
	// --------------------------------------
	// r4 r3 r2 r1 r0 
	// 
	// 最后我们把这些柱子加在一起，形成宽而重叠的分支。（a1×b4+2+3×b4+4+4×3+4×3+4×3+4×3+4×3+4×3+4+4×3+4+4×B）B）B）

	a1_19 := a1 * 19
	a2_19 := a2 * 19
	a3_19 := a3 * 19
	a4_19 := a4 * 19

	r0 := mul64(a0, b0)
	r0 = addMul64(r0, a1_19, b4)
	r0 = addMul64(r0, a2_19, b3)
	r0 = addMul64(r0, a3_19, b2)
	r0 = addMul64(r0, a4_19, b1)

	r1 := mul64(a0, b1)
	r1 = addMul64(r1, a1, b0)
	r1 = addMul64(r1, a2_19, b4)
	r1 = addMul64(r1, a3_19, b3)
	r1 = addMul64(r1, a4_19, b2)

	r2 := mul64(a0, b2)
	r2 = addMul64(r2, a1, b1)
	r2 = addMul64(r2, a2, b0)
	r2 = addMul64(r2, a3_19, b4)
	r2 = addMul64(r2, a4_19, b3)

	r3 := mul64(a0, b3)
	r3 = addMul64(r3, a1, b2)
	r3 = addMul64(r3, a2, b1)
	r3 = addMul64(r3, a3, b0)
	r3 = addMul64(r3, a4_19, b4)

	r4 := mul64(a0, b4)
	r4 = addMul64(r4, a1, b3)
	r4 = addMul64(r4, a2, b2)
	r4 = addMul64(r4, a3, b1)
	r4 = addMul64(r4, a4, b0)

	// 之后在乘法运算中，我们需要减少（携带）五个系数
	// 以获得一个四肢最多略大于2的结果⁵1，
	// 尊重元素不变量。
	// 
	// 总的来说，除
	// 更广泛的输入外，还原的效果与carryPropagate相同：我们将每个系数的进位右移
	// 51，并将其添加到其上方的肢体上。顶部进位乘以19 
	// 根据归约恒等式，并添加到最低肢体。
	// 
	// 最大系数（r0）最多为111位，这保证了
	// 所有进位最多为111-51=60位，适合uint64。
	// 
	// r0=a0×b0+19×（a1×b4+a2×b3+a3×b2+a4×b1）
	// r0<2⁵²×2⁵² + 19×(2⁵²×2⁵² + 2⁵²×2⁵² + 2⁵²×2⁵² + 2⁵²×2⁵²）
	// r0<（1+19×4）×2⁵² × 2⁵²
	// r0<2⁷ × 2⁵² × 2⁵²
	// r0<2\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\。
	// 
	// r4=a0×b4+a1×b3+a2×b2+a3×b1+a4×b0 
	// r4<5×2⁵²×2⁵²
	// r4<2⁰⁷ 
	// 

	c0 := shiftRightBy51(r0)
	c1 := shiftRightBy51(r1)
	c2 := shiftRightBy51(r2)
	c3 := shiftRightBy51(r3)
	c4 := shiftRightBy51(r4)

	rr0 := r0.lo&maskLow51Bits + c4*19
	rr1 := r1.lo&maskLow51Bits + c0
	rr2 := r2.lo&maskLow51Bits + c1
	rr3 := r3.lo&maskLow51Bits + c2
	rr4 := r4.lo&maskLow51Bits + c3

	// 现在所有系数都适合64位寄存器，但仍然太大，无法作为一个元素传递。因此，我们要做最后一个搬运链，
	// 其中的搬运将足够小，以适应2以上的摆动空间⁵¹. 
	*v = Element{rr0, rr1, rr2, rr3, rr4}
	v.carryPropagate()
}

func feSquareGeneric(v, a *Element) {
	l0 := a.l0
	l1 := a.l1
	l2 := a.l2
	l3 := a.l3
	l4 := a.l4

	// 平方运算的工作原理与上面的乘法完全相同，但由于它的
	// 对称性，我们可以将一些项组合在一起。
	// 
	// l4 l3 l2 l1 l0 x 
	// l4 l3 l2 l1 l0=
	// ---------------------------
	// l4 l3 l0 l2 l0 L10 l0 l0+
	// L4L3L3L2L3L0L3+
	// L4L4L3L4L2L4L1L0L4=
	// ----------------------------
	// r8 r7 r6 r5 r4 r3 r3 r2 r0 
	// L3L1L2L1 L10L1 19×l4l1+
	// l2l2 l1l2 l0l2 19×l4l2 19×l3l2+
	// r4 r3 r2 r1 r0 
	// 
	// 通过预计算2×19×和2×19×项，我们可以用
	// 只计算三个Mul64和四个Add64，而不是五个和八个。（l1×l4+l4+l3+l3+l3×l4×l4×l4×l3+l3+l3+l3+l3+l3+l3+l3+l3+l3+l3+l3+L10+l3+l3+l3+l3+l3+l3+l3+l3+l3+l4+l4+l4+l4+l3+l3+l3+l3+l3+l3+l3+l3+l3+l3×l3×l1=l1=l1=l1=l1=l1=l1=l1=1=1=2×4=2×4=2×3×4×10 10 10 10 10 10 10 10 10 10 10 10×4×4×4×4×4×4×4×4×4×4×4×10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 CDEFG

	l0_2 := l0 * 2
	l1_2 := l1 * 2

	l1_38 := l1 * 38
	l2_38 := l2 * 38
	l3_38 := l3 * 38

	l3_19 := l3 * 19
	l4_19 := l4 * 19

	r0 := mul64(l0, l0)
	r0 = addMul64(r0, l1_38, l4)
	r0 = addMul64(r0, l2_38, l3)

	r1 := mul64(l0_2, l1)
	r1 = addMul64(r1, l2_38, l4)
	r1 = addMul64(r1, l3_19, l3)

	r2 := mul64(l0_2, l2)
	r2 = addMul64(r2, l1, l1)
	r2 = addMul64(r2, l3_38, l4)

	r3 := mul64(l0_2, l3)
	r3 = addMul64(r3, l1_2, l2)
	r3 = addMul64(r3, l4_19, l4)

	// r4=10×l4+l1×l3+l2×l2+l3×l1+l4×l0=2×l0×l4+2×l1×l3+l2×l2 
	r4 := mul64(l0_2, l4)
	r4 = addMul64(r4, l1_2, l3)
	r4 = addMul64(r4, l2, l2)

	c0 := shiftRightBy51(r0)
	c1 := shiftRightBy51(r1)
	c2 := shiftRightBy51(r2)
	c3 := shiftRightBy51(r3)
	c4 := shiftRightBy51(r4)

	rr0 := r0.lo&maskLow51Bits + c4*19
	rr1 := r1.lo&maskLow51Bits + c0
	rr2 := r2.lo&maskLow51Bits + c1
	rr3 := r3.lo&maskLow51Bits + c2
	rr4 := r4.lo&maskLow51Bits + c3

	*v = Element{rr0, rr1, rr2, rr3, rr4}
	v.carryPropagate()
}

// carryPropagate通过应用还原
// identity（a*2²）⁵⁵ + b=a*19+b）至l4进位。
func (v *Element) carryPropagateGeneric() *Element {
	c0 := v.l0 >> 51
	c1 := v.l1 >> 51
	c2 := v.l2 >> 51
	c3 := v.l3 >> 51
	c4 := v.l4 >> 51

	v.l0 = v.l0&maskLow51Bits + c4*19
	v.l1 = v.l1&maskLow51Bits + c0
	v.l2 = v.l2&maskLow51Bits + c1
	v.l3 = v.l3&maskLow51Bits + c2
	v.l4 = v.l4&maskLow51Bits + c3

	return v
}
